home *** CD-ROM | disk | FTP | other *** search
/ PC World 2006 July & August / PCWorld_2006-07-08_cd.bin / komunikace / apache / apache_2[1].2.2-win32-x86-no_ssl.msi / Data1.cab / _ADDE6E7A5CB491FB087AA8D22EF19343 < prev    next >
Text File  |  2005-02-04  |  18KB  |  490 lines
  1. /* Copyright 2000-2005 The Apache Software Foundation or its licensors, as
  2.  * applicable.
  3.  *
  4.  * Licensed under the Apache License, Version 2.0 (the "License");
  5.  * you may not use this file except in compliance with the License.
  6.  * You may obtain a copy of the License at
  7.  *
  8.  *     http://www.apache.org/licenses/LICENSE-2.0
  9.  *
  10.  * Unless required by applicable law or agreed to in writing, software
  11.  * distributed under the License is distributed on an "AS IS" BASIS,
  12.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13.  * See the License for the specific language governing permissions and
  14.  * limitations under the License.
  15.  */
  16.  
  17. /*
  18.  * This code draws heavily from the 4.4BSD <sys/queue.h> macros
  19.  * and Dean Gaudet's "splim/ring.h".
  20.  * <http://www.freebsd.org/cgi/cvsweb.cgi/src/sys/sys/queue.h>
  21.  * <http://www.arctic.org/~dean/splim/>
  22.  *
  23.  * We'd use Dean's code directly if we could guarantee the
  24.  * availability of inline functions.
  25.  */
  26.  
  27. #ifndef APR_RING_H
  28. #define APR_RING_H
  29.  
  30. /**
  31.  * @file apr_ring.h
  32.  * @brief APR Rings
  33.  */
  34.  
  35. /*
  36.  * for offsetof()
  37.  */
  38. #include "apr_general.h"
  39.  
  40. /**
  41.  * @defgroup apr_ring Ring Macro Implementations
  42.  * @ingroup APR 
  43.  * A ring is a kind of doubly-linked list that can be manipulated
  44.  * without knowing where its head is.
  45.  * @{
  46.  */
  47.  
  48. /**
  49.  * The Ring Element
  50.  *
  51.  * A ring element struct is linked to the other elements in the ring
  52.  * through its ring entry field, e.g.
  53.  * <pre>
  54.  *      struct my_element_t {
  55.  *          APR_RING_ENTRY(my_element_t) link;
  56.  *          int foo;
  57.  *          char *bar;
  58.  *      };
  59.  * </pre>
  60.  *
  61.  * An element struct may be put on more than one ring if it has more
  62.  * than one APR_RING_ENTRY field. Each APR_RING_ENTRY has a corresponding
  63.  * APR_RING_HEAD declaration.
  64.  *
  65.  * @warning For strict C standards compliance you should put the APR_RING_ENTRY
  66.  * first in the element struct unless the head is always part of a larger
  67.  * object with enough earlier fields to accommodate the offsetof() used
  68.  * to compute the ring sentinel below. You can usually ignore this caveat.
  69.  */
  70. #define APR_RING_ENTRY(elem)                        \
  71.     struct {                                \
  72.     struct elem *next;                        \
  73.     struct elem *prev;                        \
  74.     }
  75.  
  76. /**
  77.  * The Ring Head
  78.  *
  79.  * Each ring is managed via its head, which is a struct declared like this:
  80.  * <pre>
  81.  *      APR_RING_HEAD(my_ring_t, my_element_t);
  82.  *      struct my_ring_t ring, *ringp;
  83.  * </pre>
  84.  *
  85.  * This struct looks just like the element link struct so that we can
  86.  * be sure that the typecasting games will work as expected.
  87.  *
  88.  * The first element in the ring is next after the head, and the last
  89.  * element is just before the head.
  90.  */
  91. #define APR_RING_HEAD(head, elem)                    \
  92.     struct head {                            \
  93.     struct elem *next;                        \
  94.     struct elem *prev;                        \
  95.     }
  96.  
  97. /**
  98.  * The Ring Sentinel
  99.  *
  100.  * This is the magic pointer value that occurs before the first and
  101.  * after the last elements in the ring, computed from the address of
  102.  * the ring's head.  The head itself isn't an element, but in order to
  103.  * get rid of all the special cases when dealing with the ends of the
  104.  * ring, we play typecasting games to make it look like one.
  105.  *
  106.  * Here is a diagram to illustrate the arrangements of the next and
  107.  * prev pointers of each element in a single ring. Note that they point
  108.  * to the start of each element, not to the APR_RING_ENTRY structure.
  109.  *
  110.  * <pre>
  111.  *     +->+------+<-+  +->+------+<-+  +->+------+<-+
  112.  *     |  |struct|  |  |  |struct|  |  |  |struct|  |
  113.  *    /   | elem |   \/   | elem |   \/   | elem |  \
  114.  * ...    |      |   /\   |      |   /\   |      |   ...
  115.  *        +------+  |  |  +------+  |  |  +------+
  116.  *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
  117.  *        |  next|--+     | entry|--+     |  next|--...
  118.  *        +------+        +------+        +------+
  119.  *        | etc. |        | etc. |        | etc. |
  120.  *        :      :        :      :        :      :
  121.  * </pre>
  122.  *
  123.  * The APR_RING_HEAD is nothing but a bare APR_RING_ENTRY. The prev
  124.  * and next pointers in the first and last elements don't actually
  125.  * point to the head, they point to a phantom place called the
  126.  * sentinel. Its value is such that last->next->next == first because
  127.  * the offset from the sentinel to the head's next pointer is the same
  128.  * as the offset from the start of an element to its next pointer.
  129.  * This also works in the opposite direction.
  130.  *
  131.  * <pre>
  132.  *        last                            first
  133.  *     +->+------+<-+  +->sentinel<-+  +->+------+<-+
  134.  *     |  |struct|  |  |            |  |  |struct|  |
  135.  *    /   | elem |   \/              \/   | elem |  \
  136.  * ...    |      |   /\              /\   |      |   ...
  137.  *        +------+  |  |  +------+  |  |  +------+
  138.  *   ...--|prev  |  |  +--|ring  |  |  +--|prev  |
  139.  *        |  next|--+     |  head|--+     |  next|--...
  140.  *        +------+        +------+        +------+
  141.  *        | etc. |                        | etc. |
  142.  *        :      :                        :      :
  143.  * </pre>
  144.  *
  145.  * Note that the offset mentioned above is different for each kind of
  146.  * ring that the element may be on, and each kind of ring has a unique
  147.  * name for its APR_RING_ENTRY in each element, and has its own type
  148.  * for its APR_RING_HEAD.
  149.  *
  150.  * Note also that if the offset is non-zero (which is required if an
  151.  * element has more than one APR_RING_ENTRY), the unreality of the
  152.  * sentinel may have bad implications on very perverse implementations
  153.  * of C -- see the warning in APR_RING_ENTRY.
  154.  *
  155.  * @param hp   The head of the ring
  156.  * @param elem The name of the element struct
  157.  * @param link The name of the APR_RING_ENTRY in the element struct
  158.  */
  159. #define APR_RING_SENTINEL(hp, elem, link)                \
  160.     (struct elem *)((char *)(hp) - APR_OFFSETOF(struct elem, link))
  161.  
  162. /**
  163.  * The first element of the ring
  164.  * @param hp   The head of the ring
  165.  */
  166. #define APR_RING_FIRST(hp)    (hp)->next
  167. /**
  168.  * The last element of the ring
  169.  * @param hp   The head of the ring
  170.  */
  171. #define APR_RING_LAST(hp)    (hp)->prev
  172. /**
  173.  * The next element in the ring
  174.  * @param ep   The current element
  175.  * @param link The name of the APR_RING_ENTRY in the element struct
  176.  */
  177. #define APR_RING_NEXT(ep, link)    (ep)->link.next
  178. /**
  179.  * The previous element in the ring
  180.  * @param ep   The current element
  181.  * @param link The name of the APR_RING_ENTRY in the element struct
  182.  */
  183. #define APR_RING_PREV(ep, link)    (ep)->link.prev
  184.  
  185.  
  186. /**
  187.  * Initialize a ring
  188.  * @param hp   The head of the ring
  189.  * @param elem The name of the element struct
  190.  * @param link The name of the APR_RING_ENTRY in the element struct
  191.  */
  192. #define APR_RING_INIT(hp, elem, link) do {                \
  193.     APR_RING_FIRST((hp)) = APR_RING_SENTINEL((hp), elem, link);    \
  194.     APR_RING_LAST((hp))  = APR_RING_SENTINEL((hp), elem, link);    \
  195.     } while (0)
  196.  
  197. /**
  198.  * Determine if a ring is empty
  199.  * @param hp   The head of the ring
  200.  * @param elem The name of the element struct
  201.  * @param link The name of the APR_RING_ENTRY in the element struct
  202.  * @return true or false
  203.  */
  204. #define APR_RING_EMPTY(hp, elem, link)                    \
  205.     (APR_RING_FIRST((hp)) == APR_RING_SENTINEL((hp), elem, link))
  206.  
  207. /**
  208.  * Initialize a singleton element
  209.  * @param ep   The element
  210.  * @param link The name of the APR_RING_ENTRY in the element struct
  211.  */
  212. #define APR_RING_ELEM_INIT(ep, link) do {                \
  213.     APR_RING_NEXT((ep), link) = (ep);                \
  214.     APR_RING_PREV((ep), link) = (ep);                \
  215.     } while (0)
  216.  
  217.  
  218. /**
  219.  * Splice the sequence ep1..epN into the ring before element lep
  220.  *   (..lep.. becomes ..ep1..epN..lep..)
  221.  * @warning This doesn't work for splicing before the first element or on
  222.  *   empty rings... see APR_RING_SPLICE_HEAD for one that does
  223.  * @param lep  Element in the ring to splice before
  224.  * @param ep1  First element in the sequence to splice in
  225.  * @param epN  Last element in the sequence to splice in
  226.  * @param link The name of the APR_RING_ENTRY in the element struct
  227.  */
  228. #define APR_RING_SPLICE_BEFORE(lep, ep1, epN, link) do {        \
  229.     APR_RING_NEXT((epN), link) = (lep);                \
  230.     APR_RING_PREV((ep1), link) = APR_RING_PREV((lep), link);    \
  231.     APR_RING_NEXT(APR_RING_PREV((lep), link), link) = (ep1);    \
  232.     APR_RING_PREV((lep), link) = (epN);                \
  233.     } while (0)
  234.  
  235. /**
  236.  * Splice the sequence ep1..epN into the ring after element lep
  237.  *   (..lep.. becomes ..lep..ep1..epN..)
  238.  * @warning This doesn't work for splicing after the last element or on
  239.  *   empty rings... see APR_RING_SPLICE_TAIL for one that does
  240.  * @param lep  Element in the ring to splice after
  241.  * @param ep1  First element in the sequence to splice in
  242.  * @param epN  Last element in the sequence to splice in
  243.  * @param link The name of the APR_RING_ENTRY in the element struct
  244.  */
  245. #define APR_RING_SPLICE_AFTER(lep, ep1, epN, link) do {            \
  246.     APR_RING_PREV((ep1), link) = (lep);                \
  247.     APR_RING_NEXT((epN), link) = APR_RING_NEXT((lep), link);    \
  248.     APR_RING_PREV(APR_RING_NEXT((lep), link), link) = (epN);    \
  249.     APR_RING_NEXT((lep), link) = (ep1);                \
  250.     } while (0)
  251.  
  252. /**
  253.  * Insert the element nep into the ring before element lep
  254.  *   (..lep.. becomes ..nep..lep..)
  255.  * @warning This doesn't work for inserting before the first element or on
  256.  *   empty rings... see APR_RING_INSERT_HEAD for one that does
  257.  * @param lep  Element in the ring to insert before
  258.  * @param nep  Element to insert
  259.  * @param link The name of the APR_RING_ENTRY in the element struct
  260.  */
  261. #define APR_RING_INSERT_BEFORE(lep, nep, link)                \
  262.     APR_RING_SPLICE_BEFORE((lep), (nep), (nep), link)
  263.  
  264. /**
  265.  * Insert the element nep into the ring after element lep
  266.  *   (..lep.. becomes ..lep..nep..)
  267.  * @warning This doesn't work for inserting after the last element or on
  268.  *   empty rings... see APR_RING_INSERT_TAIL for one that does
  269.  * @param lep  Element in the ring to insert after
  270.  * @param nep  Element to insert
  271.  * @param link The name of the APR_RING_ENTRY in the element struct
  272.  */
  273. #define APR_RING_INSERT_AFTER(lep, nep, link)                \
  274.     APR_RING_SPLICE_AFTER((lep), (nep), (nep), link)
  275.  
  276.  
  277. /**
  278.  * Splice the sequence ep1..epN into the ring before the first element
  279.  *   (..hp.. becomes ..hp..ep1..epN..)
  280.  * @param hp   Head of the ring
  281.  * @param ep1  First element in the sequence to splice in
  282.  * @param epN  Last element in the sequence to splice in
  283.  * @param elem The name of the element struct
  284.  * @param link The name of the APR_RING_ENTRY in the element struct
  285.  */
  286. #define APR_RING_SPLICE_HEAD(hp, ep1, epN, elem, link)            \
  287.     APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((hp), elem, link),    \
  288.                  (ep1), (epN), link)
  289.  
  290. /**
  291.  * Splice the sequence ep1..epN into the ring after the last element
  292.  *   (..hp.. becomes ..ep1..epN..hp..)
  293.  * @param hp   Head of the ring
  294.  * @param ep1  First element in the sequence to splice in
  295.  * @param epN  Last element in the sequence to splice in
  296.  * @param elem The name of the element struct
  297.  * @param link The name of the APR_RING_ENTRY in the element struct
  298.  */
  299. #define APR_RING_SPLICE_TAIL(hp, ep1, epN, elem, link)            \
  300.     APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((hp), elem, link),    \
  301.                  (ep1), (epN), link)
  302.  
  303. /**
  304.  * Insert the element nep into the ring before the first element
  305.  *   (..hp.. becomes ..hp..nep..)
  306.  * @param hp   Head of the ring
  307.  * @param nep  Element to insert
  308.  * @param elem The name of the element struct
  309.  * @param link The name of the APR_RING_ENTRY in the element struct
  310.  */
  311. #define APR_RING_INSERT_HEAD(hp, nep, elem, link)            \
  312.     APR_RING_SPLICE_HEAD((hp), (nep), (nep), elem, link)
  313.  
  314. /**
  315.  * Insert the element nep into the ring after the last element
  316.  *   (..hp.. becomes ..nep..hp..)
  317.  * @param hp   Head of the ring
  318.  * @param nep  Element to insert
  319.  * @param elem The name of the element struct
  320.  * @param link The name of the APR_RING_ENTRY in the element struct
  321.  */
  322. #define APR_RING_INSERT_TAIL(hp, nep, elem, link)            \
  323.     APR_RING_SPLICE_TAIL((hp), (nep), (nep), elem, link)
  324.  
  325. /**
  326.  * Concatenate ring h2 onto the end of ring h1, leaving h2 empty.
  327.  * @param h1   Head of the ring to concatenate onto
  328.  * @param h2   Head of the ring to concatenate
  329.  * @param elem The name of the element struct
  330.  * @param link The name of the APR_RING_ENTRY in the element struct
  331.  */
  332. #define APR_RING_CONCAT(h1, h2, elem, link) do {            \
  333.     if (!APR_RING_EMPTY((h2), elem, link)) {            \
  334.         APR_RING_SPLICE_BEFORE(APR_RING_SENTINEL((h1), elem, link),    \
  335.                   APR_RING_FIRST((h2)),            \
  336.                   APR_RING_LAST((h2)), link);        \
  337.         APR_RING_INIT((h2), elem, link);                \
  338.     }                                \
  339.     } while (0)
  340.  
  341. /**
  342.  * Prepend ring h2 onto the beginning of ring h1, leaving h2 empty.
  343.  * @param h1   Head of the ring to prepend onto
  344.  * @param h2   Head of the ring to prepend
  345.  * @param elem The name of the element struct
  346.  * @param link The name of the APR_RING_ENTRY in the element struct
  347.  */
  348. #define APR_RING_PREPEND(h1, h2, elem, link) do {            \
  349.     if (!APR_RING_EMPTY((h2), elem, link)) {            \
  350.         APR_RING_SPLICE_AFTER(APR_RING_SENTINEL((h1), elem, link),    \
  351.                   APR_RING_FIRST((h2)),            \
  352.                   APR_RING_LAST((h2)), link);        \
  353.         APR_RING_INIT((h2), elem, link);                \
  354.     }                                \
  355.     } while (0)
  356.  
  357. /**
  358.  * Unsplice a sequence of elements from a ring
  359.  * @warning The unspliced sequence is left with dangling pointers at either end
  360.  * @param ep1  First element in the sequence to unsplice
  361.  * @param epN  Last element in the sequence to unsplice
  362.  * @param link The name of the APR_RING_ENTRY in the element struct
  363.  */
  364. #define APR_RING_UNSPLICE(ep1, epN, link) do {                \
  365.     APR_RING_NEXT(APR_RING_PREV((ep1), link), link) =        \
  366.              APR_RING_NEXT((epN), link);            \
  367.     APR_RING_PREV(APR_RING_NEXT((epN), link), link) =        \
  368.              APR_RING_PREV((ep1), link);            \
  369.     } while (0)
  370.  
  371. /**
  372.  * Remove a single element from a ring
  373.  * @warning The unspliced element is left with dangling pointers at either end
  374.  * @param ep   Element to remove
  375.  * @param link The name of the APR_RING_ENTRY in the element struct
  376.  */
  377. #define APR_RING_REMOVE(ep, link)                    \
  378.     APR_RING_UNSPLICE((ep), (ep), link)
  379.  
  380.  
  381. /* Debugging tools: */
  382.  
  383. #ifdef APR_RING_DEBUG
  384. #include <stdio.h>
  385. #include <assert.h>
  386.  
  387. #define APR_RING_CHECK_ONE(msg, ptr)                    \
  388.     fprintf(stderr, "*** %s %p\n", msg, ptr)
  389.  
  390. #define APR_RING_CHECK(hp, elem, link, msg)                \
  391.     APR_RING_CHECK_ELEM(APR_RING_SENTINEL(hp, elem, link), elem, link, msg)
  392.  
  393. #define APR_RING_CHECK_ELEM(ep, elem, link, msg) do {            \
  394.     struct elem *start = (ep);                    \
  395.     struct elem *here = start;                    \
  396.     fprintf(stderr, "*** ring check start -- %s\n", msg);        \
  397.     do {                                \
  398.         fprintf(stderr, "\telem %p\n", here);            \
  399.         fprintf(stderr, "\telem->next %p\n",            \
  400.             APR_RING_NEXT(here, link));                \
  401.         fprintf(stderr, "\telem->prev %p\n",            \
  402.             APR_RING_PREV(here, link));                \
  403.         fprintf(stderr, "\telem->next->prev %p\n",            \
  404.             APR_RING_PREV(APR_RING_NEXT(here, link), link));    \
  405.         fprintf(stderr, "\telem->prev->next %p\n",            \
  406.             APR_RING_NEXT(APR_RING_PREV(here, link), link));    \
  407.         if (APR_RING_PREV(APR_RING_NEXT(here, link), link) != here) { \
  408.         fprintf(stderr, "\t*** elem->next->prev != elem\n");    \
  409.         break;                            \
  410.         }                                \
  411.         if (APR_RING_NEXT(APR_RING_PREV(here, link), link) != here) { \
  412.         fprintf(stderr, "\t*** elem->prev->next != elem\n");    \
  413.         break;                            \
  414.         }                                \
  415.         here = APR_RING_NEXT(here, link);                \
  416.     } while (here != start);                    \
  417.     fprintf(stderr, "*** ring check end\n");            \
  418.     } while (0)
  419.  
  420. #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)            \
  421.     APR_RING_CHECK_ELEM_CONSISTENCY(APR_RING_SENTINEL(hp, elem, link),\
  422.                     elem, link)
  423.  
  424. #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link) do {        \
  425.     struct elem *start = (ep);                    \
  426.     struct elem *here = start;                    \
  427.     do {                                \
  428.         assert(APR_RING_PREV(APR_RING_NEXT(here, link), link) == here); \
  429.         assert(APR_RING_NEXT(APR_RING_PREV(here, link), link) == here); \
  430.         here = APR_RING_NEXT(here, link);                \
  431.     } while (here != start);                    \
  432.     } while (0)
  433.  
  434. #else
  435. /**
  436.  * Print a single pointer value to STDERR
  437.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  438.  * @param msg Descriptive message
  439.  * @param ptr Pointer value to print
  440.  */
  441. #define APR_RING_CHECK_ONE(msg, ptr)
  442. /**
  443.  * Dump all ring pointers to STDERR, starting with the head and looping all
  444.  * the way around the ring back to the head.  Aborts if an inconsistency
  445.  * is found.
  446.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  447.  * @param hp   Head of the ring
  448.  * @param elem The name of the element struct
  449.  * @param link The name of the APR_RING_ENTRY in the element struct
  450.  * @param msg  Descriptive message
  451.  */
  452. #define APR_RING_CHECK(hp, elem, link, msg)
  453. /**
  454.  * Loops around a ring and checks all the pointers for consistency.  Pops
  455.  * an assertion if any inconsistency is found.  Same idea as APR_RING_CHECK()
  456.  * except that it's silent if all is well.
  457.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  458.  * @param hp   Head of the ring
  459.  * @param elem The name of the element struct
  460.  * @param link The name of the APR_RING_ENTRY in the element struct
  461.  */
  462. #define APR_RING_CHECK_CONSISTENCY(hp, elem, link)
  463. /**
  464.  * Dump all ring pointers to STDERR, starting with the given element and
  465.  * looping all the way around the ring back to that element.  Aborts if
  466.  * an inconsistency is found.
  467.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  468.  * @param ep   The element
  469.  * @param elem The name of the element struct
  470.  * @param link The name of the APR_RING_ENTRY in the element struct
  471.  * @param msg  Descriptive message
  472.  */
  473. #define APR_RING_CHECK_ELEM(ep, elem, link, msg)
  474. /**
  475.  * Loops around a ring, starting with the given element, and checks all
  476.  * the pointers for consistency.  Pops an assertion if any inconsistency
  477.  * is found.  Same idea as APR_RING_CHECK_ELEM() except that it's silent
  478.  * if all is well.
  479.  *   (This is a no-op unless APR_RING_DEBUG is defined.)
  480.  * @param ep   The element
  481.  * @param elem The name of the element struct
  482.  * @param link The name of the APR_RING_ENTRY in the element struct
  483.  */
  484. #define APR_RING_CHECK_ELEM_CONSISTENCY(ep, elem, link)
  485. #endif
  486.  
  487. /** @} */ 
  488.  
  489. #endif /* !APR_RING_H */
  490.